/*
leetcode 28. 找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的
第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 

提示：

1 <= haystack.length, needle.length <= 10^4
haystack 和 needle 仅由小写英文字符组成
*/

#include <iostream>
#include <string>

using namespace std;

int strStr(string haystack, string needle) {

    if (needle.empty()) return 0; // 如果 needle 为空，返回 0

    //获取字符串 haystack 和 needle 的长度，分别存储在 m 和 n 中。
    int m = haystack.size(), n = needle.size(); 
    
    // 遍历 haystack，从每个可能的位置检查是否匹配
    //m−n 是因为从 i 开始取长度为 n 的子串，i 最大为 m - n，否则越界。
    for (int i = 0; i <= m - n; i++) {
        int j = 0;
        // 比较 haystack 和 needle 对应的字符
        for (; j < n; j++) {
            //比较从 i 开始的子串与 needle 是否逐字符匹配。
            //遍历 needle 的每一个字符，与 haystack[i + j] 逐一比较。
            if (haystack[i + j] != needle[j]) {
                break; // 如果不匹配，退出内层循环
            }
        }
        //检查 j 是否等于 n。
        //如果是，表示 needle 的所有字符都匹配，返回 i，即匹配的起始位置。
        if (j == n) {
            return i; // 找到匹配项，返回起始下标
        }
    }
    return -1; // 如果没有匹配项，返回 -1
}

int main() {
    string haystack = "hello";
    string needle = "ll";

    int result = strStr(haystack, needle);
    cout << "The first match index is: " << result << endl;

    return 0;
}

/*
示例运行流程
假设输入：

haystack = "hello"
needle = "ll"
初始化阶段
m = 5，n = 2。
外层循环：
遍历 i 从 0 到 𝑚−𝑛=3。

第一轮 (i = 0)

haystack[0] = 'h', needle[0] = 'l'，不匹配，跳出内层循环。
第二轮 (i = 1)

haystack[1] = 'e', needle[0] = 'l'，不匹配，跳出内层循环。
第三轮 (i = 2)

haystack[2] = 'l', needle[0] = 'l'，匹配。
haystack[3] = 'l', needle[1] = 'l'，匹配。
内层循环结束，j = 2，满足 j == n。

返回 i = 2。

*/

